package study.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * N阶的楼梯，一次可以走一阶或两阶，有多少种走法
 */
public class ClimbStairs {

    private static final Map<Integer, Long> map = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(f(100));
        System.out.println(f(100));
    }

    static long f(int n) {
        // 如果有1阶，有一种走法
        if(n == 1)
            return 1L;
        // 如果有2阶，有两种走法（一次走2阶）（一次走1阶）
        if(n == 2)
            return 2L;

        if(!map.containsKey(n)) {
            /**
             * 第一种情况：第一步走了1阶，求剩下的（n-1）阶有多少种走法
             * 第二种情况：第一步走了2阶，求剩下的（n-2）阶有多少种走法
             *
             * 把两种情况相加
             */
            long r = f(n - 1) + f(n - 2);
            // 把计算好的结果缓存起来，避免重复计算
            map.put(n, r);
            return r;
        } else {
            return map.get(n);
        }
    }

    static long f1(int n) {
        if(n == 1 || n == 2)
            return n;
        int r = -1;
        int pp = 1, p = 2; // 前两个，前一个
        for (int i = 2; i <= n; i++) {
            r = pp + p; // 当前值等于 前两个 + 前一个 的值
            pp = p;
            p = r;
        }
        return r;
    }
}
